第 362 场力扣周赛

与车相交的点

差点又想区间合并做，看下数据范围，直接暴力，更好的做法是差分数组。

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int[] d = new int[102];
        for (var num : nums) {
            d[num.get(0)]++;
            d[num.get(1) + 1]--;
        }
        int ans = 0;
        for (int i = 1; i <= 100; i++) {
            d[i] += d[i - 1];
            if (d[i] > 0) ans++;
        }
        return ans;
    }
}

判断能否在给定时间到达单元格

题目说恰好第 \(t\) 秒到达，我还以为之前都不能到达，结果可以。那么特殊情况就是起点和终点相同，并且 \(t=1\)。

class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy && t == 1) return false;
        int a = Math.abs(sx - fx), b = Math.abs(sy - fy);
        return Math.max(a, b) <= t;
    }
}

将石头分散到网格图的最少移动次数

方法一：回溯

记录所有等于零和大于一的位置，然后 DFS 搜索每个零从哪个位置获取一。

class Solution {
    int ans = Integer.MAX_VALUE;
    
    public int minimumMoves(int[][] grid) {
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) a.add(new int[]{i, j});
                else if (grid[i][j] > 1) b.add(new int[]{i, j});
            }
        }
        dfs(0, grid, a, b, 0);
        return ans;
    }
    
    private void dfs(int i, int[][] grid, List<int[]> a, List<int[]> b, int cnt) {
        if (i == a.size()) {
            ans = Math.min(ans, cnt);
            return;
        }
        int[] p = a.get(i);
        for (int j = 0; j < b.size(); j++) {
            int[] q = b.get(j);
            if (grid[q[0]][q[1]] > 1) {
                grid[q[0]][q[1]]--;
                dfs(i + 1, grid, a, b, cnt + Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]));
                grid[q[0]][q[1]]++;
            }
        }
    }
}

方法二：状压 DP

不是很懂，具体解释可以看大佬的题解。

class Solution {
    int ans = Integer.MAX_VALUE;
    
    public int minimumMoves(int[][] grid) {
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) a.add(new int[]{i, j});
                for (int k = 2; k <= grid[i][j]; k++) b.add(new int[]{i, j});
            }
        }

        int n = a.size();
        int[] f = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) {
            f[i] = Integer.MAX_VALUE;
            int m = Integer.bitCount(i);
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    f[i] = Math.min(f[i], f[i ^ (1 << j)] + distance(a.get(m - 1), b.get(j)));
                }
            }
        }
        return f[(1 << n) - 1];
    }

    private int distance(int[] x, int[] y) {
        return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
    }
}

字符串转换

KMP + 矩阵快速幂，详细见灵神题解，学习 KMP 看代码随想录，还有各种其他解法可以看题解区（很不错！）。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int numberOfWays(String s, String t, long k) {
        int n = s.length();
        char[] text = (s + s.substring(0, n - 1)).toCharArray();
        char[] pattern = t.toCharArray();
        int c = kmp(text, pattern);

        // f[0][0] = s.equals(t) ? 1 : 0;
        // f[0][1] = s.equals(t) ? 0 : 1;
        // f[i][0] = f[i - 1][0] * (c - 1) + f[i - 1][1] * c;
        // f[i][1] = f[i - 1][0] * (n - c) + f[i - 1][1] * (n - c - 1);
        long[][] m = {{c - 1, c}, {n - c, n - c - 1}};
        m = pow(m, k);
        return s.equals(t) ? (int) m[0][0] : (int) m[0][1];
    }

    private int kmp(char[] text, char[] pattern) {
        int m = text.length, n = pattern.length;
        int[] next = new int[n];
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] == pattern[j]) j++;
            next[i] = j;
        }

        int cnt = 0;
        for (int i = 0, j = 0; i < m; i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (text[i] == pattern[j]) j++;
            if (j == n) {
                cnt++;
                j = next[j - 1];
            }
        }
        return cnt;
    }

    private long[][] pow(long[][] a, long n) {
        long[][] res = {{1, 0}, {0, 1}};
        while (n != 0) {
            if ((n & 1) == 1) res = mul(res, a);
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }

    private long[][] mul(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
            }
        }
        return c;
    }
}